При раскопках
руин был обнаружен словарь Древней Цивилизации Майя. После его анализа
оказалось, что они использовали язык, который состоял из не более чем 26 букв.
Один из нас поставил во взаимно однозначное соответствие каждой такой букве некоторую
букву английского алфавита и занес все слова из словаря в компьютер.
Порядок
расположения слов в словаре, является ли он лексикографическим, является очень
интересным вопросом для многих людей. Вам, как программисту, следует
определить, являются ли заданные слова отсортированными в некотором
лексикографическом порядке.
Замечание: В
лексикографическом порядке слово всегда стоит перед другими словами, если оно
является их префиксами. Например "ab"
предшествует "abc", "abde", и так далее.
Вход. Состоит из нескольких тестов. Каждый тест имеет следующий
формат:
n
string1
...
stringn
Каждый тест состоит из n
+ 1 строки. Первая строка каждого теста содержит целое значение n (1 ≤ n ≤ 500). i-ая
строка из следующих n строк содержит stringi, содержащую до 10 прописных букв
английского алфавита.
Последняя строка содержит "0" и не обрабатывается.
Выход. Для каждого
теста вывести в отдельной строке "yes" или "no". Если все
слова словаря могут рассматриваться таковыми, что стоят в лексикографическом
порядке, то вывести "yes". Иначе вывести "no".
|
Пример
входа |
Пример
выхода |
|
4 cba cab b a 3 bca ab a 5 abc acb b c c 5 abc acb c b b 0 |
yes no yes no |
графы -
циклы
Входные строки
состоят из букв латинского алфавита. Построим ориентированный граф из 26
вершин, каждой из которых соответствует одна буква. Далее из каждой пары
соседних слов s1 и s2 (s1 стоит во входном списке непосредственно перед s2) постараемся получить
информацию о порядке двух букв:
1. Пусть s1 = sx, s2 = sy , где s – общий префикс (возможно пустой), x и y – первые
несовпадающие буквы. Тогда положим x
< y.
2. Пусть s1 = sa, s2 = s, то есть s2 является префиксом s1. Тогда входной набор слов не представляет собой
лексикографический порядок.
3. Пусть s1 = s, s2 = sa, то есть s1 является префиксом s2. Тогда никакой информации эта пара не несет.
Для каждого
соотношения x < y проведем ориентированное ребро от x к y.
Заданные слова можно считать отсортированными в некотором лексикографическом
порядке, если граф не содержит циклов.
Двумерный массив g содержит матрицу
смежности ориентированного графа.
#define MAX 26
int g[MAX][MAX], used[MAX];
Поиск в глубину из вершины v. Цикл в ориентированном графе
существует только если в процессе поиска существует ребро, ведущее в серую
вершину (вершина считается серой, если used[i]
= 1, и черной при used[i] = 2). При
обнаружении цикла установим flag = 1.
void dfs(int
v)
{
used[v] = 1;
for(int i = 0; i < MAX; i++)
{
if
(g[v][i])
{
if
(used[i] == 1) flag = 1;
else if (!used[i]) dfs(i);
}
}
used[v] = 2;
}
Основная часть программы. Читаем
входные данные. Строим граф зависимостей.
while(scanf("%d\n",&n),
n)
{
memset(g,0,sizeof(g));
memset(used,0,sizeof(used));
flag = 0;
gets(s1);
for(j = 0; j
< n - 1; j++)
{
gets(s2);
s1 и s2 – две последовательно стоящие строки во входных данных.
temp = min(strlen(s1),strlen(s2));
for(i = 0;
i < temp; i++)
if (s1[i]
!= s2[i])
{
g[s1[i]-'a'][s2[i]-'a'] = 1;
break;
}
Если s2 является префиксом s1
(при этом s1 ≠ s2), то это не лексикографический
порядок.
if ((i ==
temp) && (strlen(s1) > strlen(s2))) flag = 1;
strcpy(s1,s2);
}
Запускаем поиск в глубину на
ориентированном графе.
for(i = 0; i
< MAX; i++)
if
(!used[i]) dfs(i);
В зависимости от значения flag выводим ответ.
puts(flag ? "no"
: "yes");
}